package day04;

/**
 * @Author Elephas
 * @Date 2022/1/7
 **/
/*
    找出数组中重复的数字。
    在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，
    也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

 */
public class Solution03 {
    final static int[] test01 = new int[]{2, 3, 1, 0, 2, 5, 3};

    public static void main(String[] args) {
        findRepeatNumber2(test01);
    }
    /*
        解法一：开一个哈希表，每个数对应数组下标的一个位置，多出来就会重复
        时间复杂度o(n),空间复杂度O(n)
     */
    public int findRepeatNumber(int[] nums) {
        int[] a = new int[nums.length];
        int i,j;
        for(i = 0; i < nums.length; i++ ){
            a[i]=0;
        }
        for(i = 0; i < nums.length; i++){
            if(a[nums[i]]==0){
                a[nums[i]]++;
            }else{
                break;
            }
        }
        return nums[i];
    }

    /*
        解法二 0-n-1 数组num中非重复元素与其对应下标相同，通过交换位置，如果发现多个元素对应一个下标，则重复
        时间复杂度o(n),空间复杂度o(1)
     */
    public static int findRepeatNumber2(int[] nums) {
        int i,temp1,temp2;
        for( i = 0 ; i < nums.length; i++){
            while(nums[i] != i){
                // 如果 当前i对应的元素不是i，分为两种情况
                // 1. nums[nums[i]] 上的元素是nums[nums[i]]，此时发现重复
                // 2. 交换位置
                if(nums[i]==nums[nums[i]]) {
                    return nums[i];
                }else{
                    temp1 = nums[i];
                    temp2 = nums[nums[i]];
                    nums[i] = temp2;
                    nums[nums[i]]=temp1;
                }
            }

        }
        return nums[i];
    }
}
